package leetcode.editor.day;

import java.util.Stack;

// 1475. 商品折扣后的最终价格
// https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/
class FinalPricesWithASpecialDiscountInAShop {
    public static void main(String[] args) {
        Solution solution = new FinalPricesWithASpecialDiscountInAShop().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 直接遍历
        /*public int[] finalPrices(int[] prices) {
            int[] ans = new int[prices.length];
            for (int i = 0; i < prices.length; i++) {
                int discount = 0;
                for (int j = i + 1; j < prices.length; j++) {
                    if (prices[j] <= prices[i]) {
                        discount = prices[j];
                        break;
                    }
                }
                ans[i] = prices[i] - discount;
            }

            return ans;
        }*/

        // 单调栈
        // 和496.下一个最大元素类似
        public int[] finalPrices(int[] prices) {
            Stack<Integer> stack = new Stack<>();
            stack.push(0);

            for (int i = 1; i < prices.length; i++) {
                while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                    Integer pop = stack.pop();
                    prices[pop] -= -prices[i];
                }
                stack.push(i);
            }

            return prices;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
